package Demo1;

import java.util.Arrays;

public class TestHeap {
    //优先级队列的实现
        private int[] elem;
        private int usedSize;
        //大根堆
        public TestHeap() {
            this.elem = new int[10];
        }
        //初始化堆
        public void initHeap(int[] array){
            for (int i = 0; i < elem.length; i++) {
                elem[i] = array[i];
                usedSize++;
            }
        }
        //最后一个父亲的下标==（数组长度-1（最后一个叶子节点）-1）/2
        //若p是最后一个父亲的下标那么p--就可以把每棵子树调整结束,c用来判断左右孩子的最大值
        //向下调整建堆O(n)
        //向上调整O（n*log2n)
        public void creatHeap(){
            for (int parent = (usedSize-1-1) / 2; parent >= 0 ; parent--) {
                shiftDown(parent,usedSize);
            }
        }//当我们采用向下调整去建堆时，时间复杂度O（n）
        private void shiftDown(int parent,int usedSize){
            int child = (2*parent)+1;//左孩子
            //判断左孩子是否合法
            while(child < usedSize){
                if(child+1 < usedSize && elem[child] < elem[child+1]){//右孩子是否合法
                    child++;
                }
                //child一定是左右孩子最大值的下标
                if(elem[child] > elem[parent]) {
                    swap(child, parent);
                    parent = child;
                    child = 2*parent+1;
                }else{
                    //本身已经是大根堆了
                    break;
                }
            }
        }
        private  void swap(int i,int j){
            int tmp = elem[i];
            elem[i] = elem[j];
            elem[j] = tmp;
        }
        //堆的插入（空间不够要扩容）
        //插入和删除都是log2（n）
        public  void offer(int val){
            if(isFull()){
                this.elem = Arrays.copyOf(elem,2*elem.length);
            }
            this.elem[usedSize] = val;//useSize=0
            //向上调整
            shiftUp(usedSize);
            usedSize++;
        }

        private void shiftUp(int child) {
            int parent = (child-1)/2;
            while(child > 0) {
                if (elem[child] > elem[parent]) {
                    swap(child,parent);
                    child = parent;
                    parent = (child-1)/2;
                } else {
                    break;
                }
            }
        }

        public boolean isFull(){
            return usedSize == elem.length;
        }
        //删除0下标的元素
        public  int poll(){
            int tmp = elem[0];
            //0下标元素和最后一个元素交换
            swap(0,usedSize-1 );
            //向下调整0~usedsize-1
            usedSize--;//删除
            shiftDown(0,usedSize);
            return tmp;
        }
        //获取堆顶元素
        public int peek()
        {
            return  this.elem[0];

        }

        //从小到大排序 对原来的数据进行排序
        //调整为大根堆
        //让第一个元素和最后一个未排序的元素进行交换
    public void heapSort(){
        int end = usedSize-1;
        while(end > 0){
            swap(0,end);
            shiftDown(0,end);
            end--;
        }
    }
}


